package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/8/17.<br><br>
 *
 * 中等：两数相除
 */
public class Topic29 {

    public static void main(String[] args) {
        Topic29 instance = new Topic29();

        System.out.println(instance.divide(10, 3));
        System.out.println(instance.divide(7, -3));
        System.out.println(instance.divide(0, 1));
        System.out.println(instance.divide(1, 1));
        System.out.println(instance.divide(-2147483648, -1));
    }

    public int divide(int dividend, int divisor) {
        int sign = 1;

        if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            sign = -1;
        }

        if(divisor == 0) {
            return Integer.MAX_VALUE;
        }

        long dividendL = Math.abs((long) dividend);
        long divisorL = Math.abs((long) divisor);

        long result = helper(dividendL, divisorL);

        if(result > Integer.MAX_VALUE) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }

        if(sign == 1) {
            return (int) result;
        }
        else {
            return -((int) result);
        }
    }

    private long helper(long dividend, long divisor) {
        if(dividend < divisor) {
            return 0;
        }

        long sum = divisor;
        long mul = 1;
        while ((sum + sum) <= dividend) {
            sum += sum;
            mul += mul;
        }

        return mul + helper(dividend - sum, divisor);
    }
}
